#pragma once
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdexcept>
#include <queue>
#include <utility>
#include <vector>
#include <sstream>
#include <string>
#include <map>
#include <set>

namespace lex
{
	struct symbol
	{
		symbol() {}
		symbol(std::string s) : s(s)
		{
			mark = s[0] == '@';
			terminal = s[0] != '$' && s[0] != '@';
		}
		bool terminal;
		bool mark;
		std::string s;
	};

	std::istream & operator>>(std::istream & is, symbol & s);
	bool operator<(symbol const& a, symbol const& b);

	struct regular_rule
	{
		symbol left;
		std::vector<symbol> right;
	};

	std::istream & operator>>(std::istream & is, regular_rule & rp);

	struct regular_grammar
	{
		void push(regular_rule const & rp);
		bool not_mark(symbol const & s) const;
		std::set<symbol> find_all_termianl(symbol const & syb) const;
		void print();

		std::set<char> alpha;
		std::multimap<symbol, regular_rule> rps;
		std::vector<symbol> marks;
	};

	std::istream & operator>>(std::istream & is, regular_grammar & g);


	namespace nfa
	{
		struct node
		{
			node(int id, bool it, int flag) : id(id), is_terminal(it), flag(flag) {}
			node() {}

			int id;
			bool is_terminal;
			int flag;
		};

		struct nfa
		{
			nfa(regular_grammar const & g);
			static symbol const epsilon;

			using state = std::set<int>;

			std::pair<state, int> closure(state const & s) const; // return type state, flag
			state trans(state const & s, char ch) const;
			void print(std::ofstream & of);

		//private:
			int alloc_node(bool terminal, int flag = 0);
			int node_index(symbol const & s);
			void find_and_add_edge(symbol const & ma, regular_grammar const & g, int flag, int now, symbol const & s = epsilon);
			void add_edge(int u, int v, std::string const & s); // "" for epsilon, and has length large than 1's terminal

			std::map<symbol, int> symbol_index;
			std::set<int> vis;
			int start;
			int alloc;
			std::set<char> alpha;
			std::vector<node> nodes;
			std::vector<std::multimap<char, int>> graph;
			std::vector<symbol> marks;
		};
	}


	namespace dfa
	{
		using state = std::set<int>;
		struct node
		{
			node(state nfa_id, int id, bool it, int flag = 0) : nfa_id(nfa_id), id(id), is_terminal(it), flag(flag) {}
			node() {}

			state nfa_id;
			int id;
			bool is_terminal;
			int flag;
		};

		struct dfa
		{
			using token_type = std::pair<std::string, std::string>;

			dfa(nfa::nfa const & n);

			void lex_init();
			token_type lex(std::string const & str, std::string::iterator & it);
			void lex(std::string const & str);
			void print(std::ofstream & of);

		// private:
			void add_edge(int u, int v, char ch) { graph[u][ch] = v; }
			int alloc_node(state const & nfa_s, int flag);
			int node_index(state const & s, int flag);

			// member for lex
			bool first = true;
			int last_ac = -1;
			int len = 0;
			int now;

			std::map<state, int> state_index;
			int start;
			int alloc;
			std::set<char> alpha;
			std::vector<node> nodes;
			std::vector<std::map<char, int>> graph;
			std::vector<symbol> marks;
		};
	}
}

